package BT_17;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Solution {
	Map<String, String> phone = new HashMap<String, String>() {
		{
			put("2", "abc");
			put("3", "def");
			put("4", "ghi");
			put("5", "jkl");
			put("6", "mno");
			put("7", "pqrs");
			put("8", "tuv");
			put("9", "wxyz");
		}
	};
	List<String> res =new LinkedList<String>();
	public List<String> letterCombinations(String digits) {
		if (digits.length() != 0) {
			BT("",digits);
		}
		return res;
	}
	private void BT(String combiantion, String nextDigits) {
		// TODO Auto-generated method stub
		if (nextDigits.length()==0) {
			res.add(combiantion);
		}else {
			String digits = nextDigits.substring(0, 1);
			String letters = phone.get(digits);
			for (int i = 0; i < letters.length(); i++) {
				String letter = phone.get(digits).substring(i, i+1);
				BT(combiantion+letter, nextDigits.substring(1));
			}
			
			
		}
		
		
		
		
	}
}
